package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/24 20:16
 */
public class FindLargestValueInEachTreeRow {

    /**
     * 层序遍历+记忆每层最大值
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {

        if (root == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        Queue<LevelOrderNode> queue = new LinkedList<>();
        queue.offer(new LevelOrderNode(root, 1));
        int levelMax = 0;
        int level = 0;
        boolean isFirst = true;
        LevelOrderNode tempNode;
        while (!queue.isEmpty()) {
            tempNode = queue.poll();

            if (tempNode.getLevel() > level) {
                if (!isFirst) {
                    result.add(levelMax);
                }
                isFirst = false;

                levelMax = tempNode.getVal().val;
                level = tempNode.getLevel();
            }

            if (tempNode.getVal().val > levelMax) {
                levelMax = tempNode.getVal().val;
            }

            if (tempNode.getVal().right != null) {
                queue.offer(new LevelOrderNode(tempNode.getVal().right, tempNode.getLevel() + 1));
            }
            if (tempNode.getVal().left != null) {
                queue.offer(new LevelOrderNode(tempNode.getVal().left, tempNode.getLevel() + 1));
            }
        }

        result.add(levelMax);

        return result;

    }
}

/**
 * 记录每个节点所在的行号
 */
class LevelOrderNode {
    private TreeNode val;
    private int level;

    public LevelOrderNode(TreeNode val, int level) {
        this.val = val;
        this.level = level;
    }

    public TreeNode getVal() {
        return val;
    }

    public void setVal(TreeNode val) {
        this.val = val;
    }

    public int getLevel() {
        return level;
    }

    public void setLevel(int level) {
        this.level = level;
    }
}
